//希尔排序

#pragma once

//希尔排序
template <typename E>
void ShellSort(E a[], int n)
{
    int dk = n / 2;
    while (dk >= 1){
        //一趟增量 dk 的希尔排序
        for(int i = dk; i < n; i++){
            E x = a[i];
            int j;
            for (j = i - dk; j >= 0 && x < a[j]; j -= dk)
            a[j + dk] = a[j];
            a[j + dk] = x;
        }

        //缩小增量
        dk /= 2;
    }
}